package LeetCode;

public class LC_473_MatchstickstoSquare {

    public static void main(String[] args) {

    }

    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {

            if (strs == null || strs.length == 0 || (m == 0 && n == 0)) return 0;
            int dp[][][] = new int[strs.length][m + 1][n + 1];
            int[][] pairs = new int[strs.length][2];

            for (int i = 0; i < strs.length; i++) {
                for (int j = 0; j < strs[i].length(); j++) {
                    char ch = strs[i].charAt(j);
                    if (ch == '0') pairs[i][0]++;
                    else pairs[i][1]++;
                }
            }
            for (int zeros = pairs[0][0]; zeros <= m; zeros++) {
                for (int ones = pairs[0][1]; ones <= n; ones++) {
                    dp[0][zeros][ones] = 1;
                }
            }
            for (int i = 1; i < strs.length; i++) {
                for (int zeros = 0; zeros <= m; zeros++) {
                    System.arraycopy(dp[i - 1][zeros], 0, dp[i][zeros], 0, n + 1);
                }
                for (int zeros = pairs[i][0]; zeros <= m; zeros++) {
                    for (int ones = pairs[i][1]; ones <= n; ones++) {
                        dp[i][zeros][ones] = Math.max(dp[i - 1][zeros][ones], 1 + dp[i - 1][zeros - pairs[i][0]][ones - pairs[i][1]]);
                    }
                }
            }
            return dp[strs.length - 1][m][n];
        }

    }

    static class Solution_2 {
        public int findMaxForm(String[] strs, int m, int n) {
            int dp[][] = new int[m + 1][n + 1];
            dp[0][0] = 0;

            for (String s : strs) {
                int zero = 0, one = 0;
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) == '0')
                        zero++;
                    else
                        one++;
                }
                for (int i = m; i > zero - 1; i--)
                    for (int j = n; j > one - 1; j--)
                        dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
            }
            return dp[m][n];
        }
    }

}